#include<vector>
#include<cctype>
#include<algorithm>
#include<queue>
#include<unordered_map>
using std::unordered_map;
using std::make_heap;
using std::pop_heap;
using std::push_heap;
using std::pair;
using std::make_pair;
using std::vector;

struct cmp {
    bool operator() (pair<int, int>& a, pair<int, int>& b) {
        return a.second >= b.second;
    }
};


class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        vector<pair<int, int>> heap;
        unordered_map<int, int> freqCounter;
        for (auto& n: nums) {
            if (freqCounter.find(n) != freqCounter.end()) freqCounter[n]++;
            else freqCounter[n] = 1;
        }
        
        for (auto iter = freqCounter.begin(); iter != freqCounter.end(); iter++) {
            if (heap.size() < k) {
                heap.push_back(make_pair(iter->first, iter->second));
                push_heap(heap.begin(), heap.end(), cmp());
            }
            else if (heap.front().second < iter->second) {
                pop_heap(heap.begin(), heap.end(), cmp());
                heap[heap.size()-1] = make_pair(iter->first, iter->second);
                push_heap(heap.begin(), heap.end(), cmp());
            }
            
        }

        vector<int> ans;
        for (auto& p: heap) {
            ans.push_back(p.first);
        }
        return ans;


    }
}; 